package algorithm.sort;

/**
 * 快速排序
 */
public class QuickSort {

    public int[] sortArray(int[] nums){

        return sort(nums , 0 , nums.length -1);
    }

    private int[] sort(int[] array, int start, int end) {
        if( array.length < 1 || start < 0 || end >= array.length || start > end ){
            return null;
        }
        //数据分割成独立的两部分时，从哪里开始区分的指示器
        int zoneIndex = partition(array , start , end);
        if (zoneIndex > start ){
            sort(array , start , zoneIndex - 1);
        }
        if (zoneIndex < end){
            sort(array , zoneIndex + 1 , end);
        }

        return array;
    }

    /**
     * 快排分区方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] array, int start, int end) {
        //只有一个元素时无需再次分区
        if(start == end){
            return start;
        }
        //随机选取一个基准数
        int pivot = (int) (start + Math.random()*(end - start - 1));
        //zoneIndex是分区指示器，初始值为分区头元素下标-1
        int zoneIndex = start - 1;
        //将基准数和分区尾元素交换位置
        swap(array , pivot , end);
        for (int i = start ; i <= end; i++) {
            //当前元素小于等于基准数
            if ( array[i] <= array[end] ){
                //首先分区指示器累加
                zoneIndex++;
                //当前元素在分区指示器右边时，交换当前元素和和分区指示器元素
                if (i > zoneIndex){
                    swap(array , i , zoneIndex);
                }
            }
        }
        return zoneIndex;
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
